package com.gaogzhen.datastructure.tree;

import com.gaogzhen.datastructure.queue.LinkQueue;
import com.gaogzhen.datastructure.queue.Queue;
import com.gaogzhen.datastructure.stack.Stack;

import java.util.*;

/**
 * 二叉搜索树非递归实现
 *  每个节点存储单个对象E
 * @author Administrator
 * @param <E> 泛型
 */
public class BinarySearchTree<E extends Comparable<E>> {

    transient TreeNode<E> root;
    transient int size;

    private static class TreeNode<E> {
        E item;
        TreeNode<E> left;
        TreeNode<E> right;

        TreeNode(TreeNode<E> left, E item, TreeNode<E> right) {
            this.item = item;
            this.left = left;
            this.right = right;
        }
    }

    public BinarySearchTree() {
    }

    // 空值检测
    public void checkNull(Object o) {
        if (o == null)
            throw new NullPointerException("数据不能为空");
    }

    // 添加
    public boolean add(E e) {
        checkNull(e);

        if (root == null) {
            root = new TreeNode<>(null, e, null);
            size++;
            return true;
        }
        TreeNode<E> parent;
        TreeNode<E> current = root;
        while (true) {
            parent = current;
            if (e.compareTo(parent.item) == 0)
                return false;
            else if (e.compareTo(parent.item) < 0) {
                current = current.left;
                if (current == null) {
                    parent.left = new TreeNode<>(null, e, null);
                    size++;
                    return true;
                }
            } else {
                current = current.right;
                if (current == null) {
                    parent.right = new TreeNode<>(null, e, null);
                    size++;
                    return true;
                }
            }
        }
    }

    /**
     * 删除
     * @param o 目标
     * @return  要删除的值
     */
    public E remove(E o) {

        // 如果目标元素为空或者树为空
        if (o == null ||root == null)
            return null;
        // 查找要删除的元素
       TreeNode<E> parent = null;
       TreeNode<E> current = root;
       while (current != null) {
           if (current.item.compareTo(o) < 0) {
               parent = current;
               current = current.right;
           }
           else if (current.item.compareTo(o) > 0) {
               parent = current;
               current = current.left;
           }
           else
               break;
       }
        // 删除
        // 不存在
        if (current == null)
            return null;
        TreeNode<E> old = current;
        E item = old.item;
        // 有左右子树,用后继节点替换目标节点
        if (current.left != null && current.right != null) {
            parent = current;
            current = current.right;
            while (current.left != null) {
                parent = current;
                current = current.left;
            }
            old.item = current.item;
        }

        // 最多有一个子树
        old = current.left;
        if (old == null)
            old = current.right;
        if (parent == null) {
            root = old;
        } else {
            if (parent.left == current)
                parent.left = old;
            else
                parent.right = old;
        }

        // 删除元素置空
        current.item = null;
        current.left = null;
        current.right = null;

        size--;

        return item;
    }

    public int size() {
        return size;
    }

    public E getMax() {
        return getMax(root);
    }
    public E getMax(TreeNode<E> node) {
        if (node == null)
            return null;
        TreeNode<E> parent = null;
        TreeNode<E> current = node;
        while (current != null) {
            parent = current;
            current = current.right;
        }

        return parent.item;
    }



    public boolean isEmpty() {
        return size == 0;
    }

    public E getMin() {
        return getMin(root);
    }
    public E getMin(TreeNode<E> node) {
        if (node == null)
            return null;
        TreeNode<E> parent = null;
        TreeNode<E> current = node;
        while (current != null) {
            parent = current;
            current = current.left;
        }

        return parent.item;

    }

    /**
     * 前序遍历
     * @return  迭代器
     */
    public Iterable<E> preTraversal() {
        Queue<E> q = new LinkQueue<>();
        Stack<TreeNode<E>> l = new Stack<>();
        l.push(root);
        while (!l.isEmpty()) {
            TreeNode<E> pop = l.pop();
            q.offer(pop.item);
            if (pop.right != null)
                l.push(pop.right);
            if (pop.left != null)
                l.push(pop.left);
        }

        return q;
    }

    /**
     * 中序遍历
     * @return  中序遍历迭代器
     */
    public Iterable<E> midTraversal() {
        return midTraversal(root);
    }

    public Iterable<E> midTraversal(TreeNode<E> node) {
        Queue<E> q = new LinkQueue<>();

        Stack<TreeNode<E>> l = new Stack<>();
        TreeNode<E> cur = node;

        while (cur != null || !l.isEmpty()) {
            while (cur != null) {
                l.push(cur);
                cur = cur.left;
            }
            if (!l.isEmpty()) {
                cur = l.pop();
                q.offer(cur.item);
                cur = cur.right;
            }
        }

      return q;
    }

    /**
     * 后序遍历
     * @return  后序遍历迭代器
     */
    public Iterable<E> postTraversal() {
       Queue<E> q = new LinkQueue<>();

       Stack<TreeNode<E>> stack = new Stack<>();
       TreeNode<E> pre = root;
       TreeNode<E> cur = root;
       while (cur != null || !stack.isEmpty()) {
           while (cur != null) {
               stack.push(cur);
               cur = cur.left;
           }
           if (!stack.isEmpty()) {
               cur = stack.peek().right;
               if (cur == null || pre == cur) {
                   pre = stack.pop();
                   q.offer(pre.item);
                   cur = null;
               }
           }
       }

       return q;
    }

    /**
     * 获取树高度(深度)
     * @return  树的高度(深度)
     */
    public int level() {
        int level = 0;
        int i = 0;
        Stack<TreeNode<E>> stack = new Stack<>();
        TreeNode<E> pre = root;
        TreeNode<E> current = root;
        while (current != null || !stack.isEmpty()) {
            while (current != null) {
                stack.push(current);
                current = current.left;
                i++;
                if (i > level)
                    level = i;
            }
            if (!stack.isEmpty()) {
                current = stack.peek().right;
                if (current == null || pre == current) {
                    pre = stack.pop();
                    current = null;
                    i--;
                }
            }
        }

        return level;
    }

    /**
     * 层序遍历
     * @return  层序遍历迭代器
     */
    public Iterable<E> levelTraversal() {
        Queue<E> q = new LinkQueue<>();
        Queue<TreeNode<E>> l = new LinkQueue<>();
        l.offer(root);
        while (!l.isEmpty()) {
            TreeNode<E> pop = l.poll();
            q.offer(pop.item);
            if (pop.left != null)
                l.offer(pop.left);
            if (pop.right != null)
                l.offer(pop.right);
        }

        return q;
    }

    /**
     * 迭代
     */
    private class Itr implements Iterator<E> {

        Iterator<E> iterator;

        Itr() {
           iterator = midTraversal().iterator();
        }

        @Override
        public boolean hasNext() {
            return iterator.hasNext();
        }

        @Override
        public E next() {
            return iterator.next();
        }
    }

    @Override
    public String toString() {
        Iterator<E> iterator = new Itr().iterator;
        if (!iterator.hasNext())
            return "[]";
        StringBuilder b = new StringBuilder("[");
        while (true) {
            E next = iterator.next();
            b.append(next);
            if (!iterator.hasNext()) {
                return b.append("]").toString();
            }
            b.append(",");
        }
    }
}
